package DynamicProgramming;//
//
// 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿
//过地下城并通过对抗恶魔来拯救公主。 
//
// 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 
//
// 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么
//包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 
//
// 为了尽快到达公主，骑士决定每次只向右或向下移动一步。 
//
// 
//
// 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 
//
// 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。 
//
// 
// 
// -2 (K) 
// -3 
// 3 
// 
// 
// -5 
// -10 
// 1 
// 
// 
// 10 
// 30 
// -5 (P) 
// 
// 
//
//
// 
//
// 说明: 
//
// 
// 
// 骑士的健康点数没有上限。 
// 
// 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。 
// Related Topics 数组 动态规划 矩阵 👍 617 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class calculateMinimumHP {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        //dp[i][j]代表到达该位置至少需要多少血
        int[][] dp = new int[m][n];

        for(int i = m-1 ; i >= 0 ; i--){
            for(int j = n-1 ; j>= 0 ; j--){
                //baseCase:终点位置的血量先定好
                //如果终点需要扣血，那么需要到达该位置时血量为刚好扣完还剩一点血
                //如果终点位置不需要扣血，只要保证活下来就行(刚好剩下一点血)
                if(i == m-1 && j == n-1){
                    if(dungeon[i][j] < 0){
                        dp[i][j] = Math.abs(dungeon[i][j])+1;
                    }else{
                        dp[i][j] = 1;
                    }
                }else{
                    //获取右边格子和下边格子的至少需要血量值，选择较小的那一个格子
                    int a = i+1 == m ? Integer.MAX_VALUE : dp[i+1][j];
                    int b = j+1 == n ? Integer.MAX_VALUE : dp[i][j+1];
                    int now = Math.min(a,b);
                    //用当前格子的值与较小需要的血量值比较，
                    //如果当前的值大于等于较小需要的血量，那么就是说在当前格补上血后必能解决下一个的血量需求，那么只需要到达当前格就好了（即至少需要血量设置为1）
                    //如果当前的值小于较小需要的血量，那么必须解决当前格子的问题同时还要解决下一个的血量需求，那么就需要“提前拥有这么多血”，加的血量为下一个格子需求的血量减去当前格子的值
                    if(dungeon[i][j] >= now){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = now - dungeon[i][j];
                    }
                }
            }
        }

        return dp[0][0];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
